「Note」整体二分

Posted on Edited on

比 cdq 阳间多了 ！！！1

$\mathcal{Dynamic \ Rankings}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

整体二分却也是个比较好懂的算法。
大概就是用递归代替 while ，实现多线程推进。
然后把修改替换成删除和添加。
注释写在代码里

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 6e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, cnt, qcnt, num[MAXN], ans[MAXN], bit[MAXN];
struct Question { int l, r, k, op, ind; } q[MAXN], q1[MAXN], q2[MAXN];

int lowbit(int x) { return x & -x; }
void update(int x, int val) { for (int i = x; i <= n; i += lowbit(i)) bit[i] += val; }
int query(int x) {
	int res = 0;
	for (int i = x; i; i -= lowbit(i)) res += bit[i];
	return res;
}

void solve(int vall, int valr, int optl, int optr) {
	if (optl > optr) return;
	if (vall == valr) {
		for (int i = optl; i <= optr; i++) if (q[i].op == 2) ans[q[i].ind] = vall;
		return;
	}

	int mid = (vall + valr) >> 1, cnt1 = 0, cnt2 = 0;
	for (int i = optl; i <= optr; i++) {
		if (q[i].op == 1) { // 对于  删 / 加  操作
			if (q[i].l <= mid) q1[++cnt1] = q[i], update(q[i].ind, q[i].r);  // 统计 <= mid 的做出贡献
			else q2[++cnt2] = q[i];
		} else {
			int tmp = query(q[i].r) - query(q[i].l - 1);
			if (q[i].k > tmp) q[i].k -= tmp, q2[++cnt2] = q[i];
			else q1[++cnt1] = q[i];
		}
	}

	for (int i = 1; i <= cnt1; i++) q[optl + i - 1] = q1[i];
	for (int i = 1; i <= cnt2; i++) q[optl + cnt1 + i - 1] = q2[i]; 
	for (int i = 1; i <= cnt1; i++) if (q1[i].op == 1) update(q1[i].ind, -q1[i].r);  // 注意每层都要还原

	solve(vall, mid, optl, optl + cnt1 - 1);
	solve(mid + 1, valr, optl + cnt1, optr);

}

int main() {

	scanf("%d %d", &n, &m);
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x); num[i] = x;
		q[++cnt] = Question{x, 1, 0, 1, i};
	}
	for (int i = 1, l, r, k, x, y; i <= m; i++) {
		char opt; cin >> opt;
		if (opt == 'Q') scanf("%d %d %d", &l, &r, &k), q[++cnt] = Question{l, r, k, 2, ++qcnt};
		else {
			scanf("%d %d", &x, &y); // 拆成  删除 / 添加
			q[++cnt] = Question{num[x], -1, 0, 1, x}, num[x] = y;
			q[++cnt] = Question{num[x], 1, 0, 1, x};
		}
	}

	solve(-INF, INF, 1, cnt);
	for (int i = 1; i <= qcnt; i++) printf("%d\n", ans[i]);

	return 0;
}

$\mathcal{[ZJOI2013]K大数查询}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

这道题要把上一题的单修改成区修就好了。
主要开 long long 。

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 5e4 + 5;
const LL INF = 1e18;

int n, m, qcnt;
LL ans[MAXN];

struct SegmentTree { int l, r; LL dat, tag; } s[MAXN << 4];
void push_up(int p) { s[p].dat = (s[p << 1].dat + s[p << 1 | 1].dat); }
void push_down(int p) {
	if (!s[p].tag) return;
	s[p << 1].dat += (s[p << 1].r - s[p << 1].l + 1) * s[p].tag, s[p << 1].tag += s[p].tag;
	s[p << 1 | 1].dat += (s[p << 1 | 1].r - s[p << 1 | 1].l + 1) * s[p].tag, s[p << 1 | 1].tag += s[p].tag;
	s[p].tag = 0;
}
void build(int p, int l, int r) {
	s[p].l = l, s[p].r = r;
	if (l == r) { s[p].dat = 0; return; }
	int mid = (l + r) >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	push_up(p);
}
void update(int p, int l, int r, LL add) {
	if (s[p].l >= l && s[p].r <= r) {
		s[p].dat += (s[p].r - s[p].l + 1) * add, s[p].tag += add;
		return;
	}
	push_down(p);
	int mid = (s[p].l + s[p].r) >> 1;
	if (l <= mid) update(p << 1, l, r, add);
	if (r > mid) update(p << 1 | 1, l, r, add);
	push_up(p);
}
LL query(int p, int l, int r) {
	if (s[p].l >= l && s[p].r <= r) return s[p].dat;
	push_down(p);
	int mid = (s[p].l + s[p].r) >> 1, res = 0;
	if (l <= mid) res += query(p << 1, l, r);
	if (r > mid) res += query(p << 1 | 1, l, r);
	return res;
}

struct Question { int l, r, ind, op; LL c; } q[MAXN], q1[MAXN], q2[MAXN];

void solve(LL vall, LL valr, int optl, int optr) {
	if (optl > optr) return;
	if (vall == valr) {
		for (int i = optl; i <= optr; i++) if (q[i].op == 2) ans[q[i].ind] = vall;
		return;
	}
	LL mid = (vall + valr) >> 1; int cnt1 = 0, cnt2 = 0;
	for (int i = optl; i <= optr; i++) {
		if (q[i].op == 1) {
			if (q[i].c <= mid) q1[++cnt1] = q[i];
			else update(1, q[i].l, q[i].r, 1), q2[++cnt2] = q[i];
		} else {
			LL tmp = query(1, q[i].l, q[i].r);
			if (q[i].c > tmp) q[i].c -= tmp, q1[++cnt1] = q[i];
			else q2[++cnt2] = q[i];
		}
	}
	for (int i = 1; i <= cnt1; i++) q[optl + i - 1] = q1[i];
	for (int i = 1; i <= cnt2; i++) q[optl + cnt1 + i - 1] = q2[i];
	for (int i = 1; i <= cnt2; i++) if (q2[i].op == 1) update(1, q2[i].l, q2[i].r, -1);
	solve(vall, mid, optl, optl + cnt1 - 1), solve(mid + 1, valr, optl + cnt1, optr);
}

int main() {

	scanf("%d %d", &n, &m);
	build(1, 1, n);
	for (int i = 1, opt, l, r; i <= m; i++) { LL c;
		scanf("%d %d %d %lld", &opt, &l, &r, &c);
		if (opt == 1) q[i] = Question{l, r, i, 1, c};
		else q[i] = Question{l, r, ++qcnt, 2, c};
	}
	solve(-INF, INF, 1, m);
	for (int i = 1; i <= qcnt; i++) printf("%lld\n", ans[i]);

	return 0;
}

$\mathcal{Sign \ on \ Fence}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

把求值转化成判定就好了，大概是个 trick 。
把问题变成查询是否有大于等于 mid 且长度不少于 k 的子区间。
然后就要线段树来维护一段最长的 0/1 区间。
于是题目就变成了 SHOI2015脑洞治疗仪 + 整体二分。

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, cnt, ans[MAXN];

struct SegmentTree { int l, r, dat, lmax, rmax; } s[MAXN << 2];
void push_up(int p) {
	s[p].lmax = max((s[p << 1].lmax == s[p << 1].r - s[p << 1].l + 1) * s[p << 1 | 1].lmax + s[p << 1].lmax, s[p << 1].lmax);
	s[p].rmax = max((s[p << 1 | 1].rmax == s[p << 1 | 1].r - s[p << 1 | 1].l + 1) * s[p << 1].rmax + s[p << 1 | 1].rmax, s[p << 1 | 1].rmax);
	s[p].dat = max(max(s[p << 1].dat, s[p << 1 | 1].dat), s[p << 1].rmax + s[p << 1 | 1].lmax);
}
void build(int p, int l, int r) {
	s[p].l = l, s[p].r = r;
	if (l == r) {
		s[p].dat = s[p].lmax = s[p].rmax = 0;
		return;
	}
	int mid = (s[p].l + s[p].r) >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	push_up(p);
}
void update(int p, int x, int val) {
	if (s[p].l == s[p].r) {
		s[p].dat = s[p].lmax = s[p].rmax = val;
		return;
	}
	int mid = (s[p].l + s[p].r) >> 1;
	if (x <= mid) update(p << 1, x, val);
	if (x > mid) update(p << 1 | 1, x, val);
	push_up(p);
}
int query(int p, int l, int r) {
	if (s[p].l >= l && s[p].r <= r) return s[p].dat;
	int mid = (s[p].l + s[p].r) >> 1, lmax = 0, rmax = 0, addl = 0, addr = 0;
	if (l <= mid) {
		lmax = query(p << 1, l, r);
		if (r > mid) addl = min(mid - l + 1, s[p << 1].rmax);
	}
	if (r > mid) {
		rmax = query(p << 1 | 1, l, r);
		if (l <= mid) addr = min(r - mid, s[p << 1 | 1].lmax);
	}
	return max(addl + addr, max(lmax, rmax));
}

struct Question { int l, r, k, op, ind; } q[MAXN], q1[MAXN], q2[MAXN];

void solve(int vall, int valr, int optl, int optr) {
	if (optl > optr) return;
	if (vall == valr) {
		for (int i = optl; i <= optr; i++) if (q[i].op == 2) ans[q[i].ind] = vall;
		return;
	}
	int mid = (vall + valr) >> 1, cnt1 = 0, cnt2 = 0;
	for (int i = optl; i <= optr; i++) {
		if (q[i].op == 1) {
			if (q[i].l > mid) update(1, q[i].ind, 1), q2[++cnt2] = q[i];
			else q1[++cnt1] = q[i];
		} else {
			int tmp = query(1, q[i].l, q[i].r);
			if (tmp >= q[i].k) q2[++cnt2] = q[i];
			else q1[++cnt1] = q[i];
		}
	}
	for (int i = 1; i <= cnt1; i++) q[optl + i - 1] = q1[i];
	for (int i = 1; i <= cnt2; i++) q[optl + cnt1 + i - 1] = q2[i];
	solve(vall, mid, optl, optl + cnt1 - 1);
	for (int i = optl + cnt1; i <= optr; i++) if (q[i].op == 1) update(1, q[i].ind, 0);
	solve(mid + 1, valr, optl + cnt1, optr);
}

int main() {

	scanf("%d", &n);
	build(1, 1, n);

	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		q[++cnt] = Question{x, 1, 0, 1, i};
	}
	scanf("%d", &m);
	for (int i = 1, l, r, k; i <= m; i++) {
		scanf("%d %d %d", &l, &r, &k);
		q[++cnt] = Question{l, r, k, 2, i};
	}
	solve(-INF, INF, 1, cnt);

	for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);

	return 0;
}

$\mathcal{THUPC2017 \ 天天爱射击}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

首先吐槽题面。
题目可以把子弹看成修改，把木板看成查询。
可以直接上手了。
主要在修改答案时改为统计每个修改造成贡献的查询有多少个。

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 4e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, up, cnt, x1[MAXN], x2[MAXN], cou[MAXN], ans[MAXN], bit[MAXN];
int lowbit(int x) { return x & -x; }
void update(int x, int val) { for (int i = x; i <= up; i += lowbit(i)) bit[i] += val; }
int query(int x) {
	int res = 0;
	for (int i = x; i; i -= lowbit(i)) res += bit[i];
	return res;
}

struct Question { int l, r, k, op, ind; } q[MAXN], q1[MAXN], q2[MAXN];

void solve(int vall, int valr, int optl, int optr) {
	if (optl > optr) return;
	if (vall == valr) {
		for (int i = optl; i <= optr; i++) if (q[i].op == 2) ans[vall]++;
		return;
	}
	int mid = (vall + valr) >> 1, cnt1 = 0, cnt2 = 0;
	for (int i = optl; i <= optr; i++) {
		if (q[i].op == 1) {
			if (q[i].ind <= mid) update(q[i].l, 1), q1[++cnt1] = q[i];
			else q2[++cnt2] = q[i];
		} else {
			int tmp = query(q[i].r) - query(q[i].l - 1);
			if (q[i].k <= tmp) q1[++cnt1] = q[i];
			else q[i].k -= tmp, q2[++cnt2] = q[i];
		}
	}
	for (int i = 1; i <= cnt1; i++) q[optl + i - 1] = q1[i];
	for (int i = 1; i <= cnt2; i++) q[optl + cnt1 + i - 1] = q2[i];
	for (int i = 1; i <= cnt1; i++) if (q1[i].op == 1) update(q1[i].l, -1);
	solve(vall, mid, optl, optl + cnt1 - 1);
	solve(mid + 1, valr, optl + cnt1, optr);
}

int main() {

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d %d %d", &x1[i], &x2[i], &cou[i]), up = max(up, x2[i]);
	for (int i = 1, x; i <= m; i++) scanf("%d", &x), q[++cnt] = Question{x, 1, 0, 1, i};
	for (int i = 1; i <= n; i++) q[++cnt] = Question{x1[i], x2[i], cou[i], 2, i};
	solve(0, n + 1, 1, cnt);

	for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);

	return 0;
}

$\mathcal{Till \ I \ Collapse}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

大概是个整体二分？
你会发现答案单调，且最多只有 $\sqrt n $ 种答案取值。
然后可以搞一个神奇的二分模板套上去算它。

$\mathcal{Template}$

1
2
3
4
5
6
7
8
9
void solve(int l, int r) {
	int lnum = check(l), rnum = check(r);
	if (lnum == rnum) {
		for (int i = l; i <= r; i++) ans[i] = lnum;
		return;
	}
	int mid = (l + r) >> 1;
	solve(l, mid), solve(mid + 1, r);
}

时间复杂度是 $\mathcal{O}(\sqrt n \log n)$ 。

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;

int n, len, dp[MAXN], fa[MAXN], dfn[MAXN], ans[MAXN];
vector<int> G[MAXN];
bool vis[MAXN];

void dfs(int u, int fath) {
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (v == fath) continue;
		dfs(v, u);
	}
	fa[u] = fath, dfn[++len] = u;
}

int check(int k) {
	
	for (int i = 1; i <= n; i++) dp[i] = 1, vis[i] = 0;

	int sum = 0;
	for (int i = 1; i <= n; i++) if (!vis[dfn[i]] && !vis[fa[dfn[i]]] && fa[dfn[i]]) {
		if (dp[fa[dfn[i]]] + dp[dfn[i]] >= k) {
			sum++, vis[fa[dfn[i]]] = 1;
		} else dp[fa[dfn[i]]] = max(dp[fa[dfn[i]]], dp[dfn[i]] + 1);
	}
	return sum;

}

void solve(int l, int r) {
	int lnum = check(l), rnum = check(r);
	if (lnum == rnum) {
		for (int i = l; i <= r; i++) ans[i] = lnum;
		return;
	}
	int mid = (l + r) >> 1;
	solve(l, mid), solve(mid + 1, r);
}

int main() {

	scanf("%d", &n);
	for (int i = 1, u, v; i < n; i++) {
		scanf("%d %d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	dfs(1, 0), solve(1, n);

	ans[1] = n;
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);

	return 0;
}

$\mathcal{You \ Are \ Given \ a \ Tree}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

与上一题类似。
只不过在树上，先 dfs 出 dfn 序，搞一个在 dfn 序上的 dp 就好了。

$\mathcal{Code}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;

int n, len, dp[MAXN], fa[MAXN], dfn[MAXN], ans[MAXN];
vector<int> G[MAXN];
bool vis[MAXN];

void dfs(int u, int fath) {
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (v == fath) continue;
		dfs(v, u);
	}
	fa[u] = fath, dfn[++len] = u;
}

int check(int k) {
	
	for (int i = 1; i <= n; i++) dp[i] = 1, vis[i] = 0;

	int sum = 0;
	for (int i = 1; i <= n; i++) if (!vis[dfn[i]] && !vis[fa[dfn[i]]] && fa[dfn[i]]) {
		if (dp[fa[dfn[i]]] + dp[dfn[i]] >= k) {
			sum++, vis[fa[dfn[i]]] = 1;
		} else dp[fa[dfn[i]]] = max(dp[fa[dfn[i]]], dp[dfn[i]] + 1);
	}
	return sum;

}

void solve(int l, int r) {
	int lnum = check(l), rnum = check(r);
	if (lnum == rnum) {
		for (int i = l; i <= r; i++) ans[i] = lnum;
		return;
	}
	int mid = (l + r) >> 1;
	solve(l, mid), solve(mid + 1, r);
}

int main() {

	scanf("%d", &n);
	for (int i = 1, u, v; i < n; i++) {
		scanf("%d %d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	dfs(1, 0), solve(1, n);

	ans[1] = n;
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);

	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」